// NC50 链表中的节点每k个一组翻转
// https://www.nowcoder.com/practice/b49c3dc907814e9bbfa8437c251b028e
//单链表反转1：
// init. 当前节点=head
// init. 末节点=nullptr
// while. 保存secondNode
//当前节点next=末节点
//末节点更新为当前
//当前更新为第二

//单链表反转2：栈
// 一组k个进栈,不足break
// if 进栈数=k，反转
// link剩余
#include <deque>
using namespace std;

struct ListNode {
  ListNode(int x) : val(x), next(nullptr) {}
  int val;
  struct ListNode* next;
};

int getLen(ListNode* head) {
  int i = 0;
  while (head) {
    head = head->next;
    i++;
  }
  return i;
}

// 方法1
ListNode* reverseKGroup_1(ListNode* head, int k) {
  // write code here
  if (head == nullptr || head->next == nullptr || k <= 1) {
    return head;
  }
  int len = getLen(head);  //  10  6
  int sx = len / k;
  ListNode* res = new ListNode(0);
  ListNode* now = res;
  for (int i = 0; i < sx; i++) {   // group4: 1->2->3->4  lastNode(4)
    ListNode* lastNode = nullptr;  // lastNode of last cycle
    for (int j = 0; j < k; j++) {
      ListNode* secondNode = head->next;  // backup
      head->next = lastNode;
      lastNode = head;
      head = secondNode;  // head move to next node
    }
    now->next = lastNode;
    while (now->next) {
      now = now->next;
    }
  }
  now->next = head;
  return res->next;
}

int LinkLength(ListNode* head) {
  int i = 0;
  while (head) {
    head = head->next;
    i++;
  }
  return i;
}

// 方法2
ListNode* reverseKGroup_deque(ListNode* head, int k) {
  // write code here
  if (k <= 1 || head == nullptr) {
    return head;
  }
  deque<ListNode*> deqNode;
  ListNode* res = new ListNode(0);
  ListNode* now = res;
  while (true) {
    int count = 0;
    for (int i = 0; i < k; i++) {
      deqNode.push_back(head);
      head = head->next;
      count++;
      if (head == nullptr) {
        break;
      }
    }
    if (count == k) {
      while (!deqNode.empty()) {
        now->next = deqNode.back();
        deqNode.pop_back();
        now = now->next;
        now->next = nullptr;
      }
    }
    if (head == nullptr) {
      break;
    }
  }
  ListNode* end = nullptr;
  while (!deqNode.empty()) {
    end = deqNode.back();
    deqNode.pop_back();
  }
  now->next = end;
  return res->next;
}
